/*================================================================
*   Copyright (C) 2023 baichao All rights reserved.
*
*   文件名称：main2.c
*   创 建 者：baichao
*   创建日期：2023年12月28日
*   描    述：
*
================================================================*/

/*
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s
 * 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。 注意： 对于 t
 * 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s
 * 中存在这样的子串，我们保证它是唯一的答案。
 *
 * 示例 1：
 *   输入：s = "ADOBECODEBANC", t = "ABC"
 *   输出："BANC"
 *   解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
 *
 * 示例 2：
 *   输入：s = "a", t = "a"
 *   输出："a"
 *   解释：整个字符串 s 是最小覆盖子串。
 *
 * 示例 3:
 *   输入: s = "a", t = "aa"
 *   输出: ""
 *   解释: t 中两个字符 'a' 均应包含在 s
 * 的子串中，因此没有符合条件的子字符串，返回空字符串。
 *
 * 提示：
 *   m == s.length
 *   n == t.length
 *   1 <= m, n <= 105
 *   s 和 t 由英文字母组成
 *
 * 进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？
 */

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char *minWindow(char *s, char *t) {
  int32_t s_len = strlen(s);
  int32_t t_len = strlen(t);

  if (s_len < t_len) {
    return "";
  }

  // 构造字符计数数组
  int32_t substringCharCountArray[58] = {0};
  int32_t stringCharCountArray[58] = {0};
  for (int32_t i = 0; i < t_len; i++) {
    substringCharCountArray[t[i] - 'A']++;
  }

  // 定义窗口的左右指针和最小覆盖子串的起始索引和长度
  int32_t left = 0, right = 0;
  int32_t minStart = 0, minLen = s_len + 1;
  int32_t count = 0;

  while (right < s_len) {
    // 扩展窗口
    if (substringCharCountArray[s[right] - 'A'] > 0) {
      stringCharCountArray[s[right] - 'A']++;
      if (stringCharCountArray[s[right] - 'A'] <=
          substringCharCountArray[s[right] - 'A']) {
        count++;
      }
    }
    right++;

    // 收缩窗口
    while (count == t_len) {
      if (right - left < minLen) {
        minLen = right - left;
        minStart = left;
      }
      if (substringCharCountArray[s[left] - 'A'] > 0) {
        stringCharCountArray[s[left] - 'A']--;
        if (stringCharCountArray[s[left] - 'A'] <
            substringCharCountArray[s[left] - 'A']) {
          count--;
        }
      }
      left++;
    }
  }

  // 根据最小覆盖子串的起始索引和长度构造结果字符串
  if (minLen <= s_len) {
    char *result = (char *)malloc((minLen + 1) * sizeof(char));
    strncpy(result, s + minStart, minLen);
    result[minLen] = '\0';
    return result;
  }

  return "";
}

int main() {
  char *s = "ADOBECODEBANC";
  char *t = "ABC";
  char *result = minWindow(s, t);
  printf("%s\n", result);
  free(result);

  return 0;
}
